package offer2

/**
https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/

剑指 Offer 56 - I. 数组中数字出现的次数
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2：
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
*/

// 56：1.数组中数字出现的次数
func singleNumbers(nums []int) []int {

	var acc int //将数组元素遍历, 都进行异或处理
	for _, n := range nums {
		acc ^= n
	}

	diff := 1 //求出两个数字第一位不相同的位置
	for diff&acc == 0 {
		diff <<= 1
	}

	res1, res2 := 0, 0
	for _, n := range nums { //遍历每个元素, 该元素&diff, 如果为0, 放入1结果集, 如果是1, 放入2结果集   由于其它元素都是出现两次, 都会被自己消除掉
		if diff&n != 0 {
			res1 ^= n
		} else {
			res2 ^= n
		}
	}

	return []int{res1, res2} //将剩下的 res1, res2返回即可
}
